소수찾기

NOTE

프로그래머스 · 완전탐색(순열 DFS + 백트래킹 + 소수 판별) 숫자 문자열로 만들 수 있는 모든 순열 조합을 DFS로 생성하고, Set으로 중복을 제거한 뒤 각 수가 소수인지 판별해 개수를 센다.

📝 문제

• 숫자 문자열이 주어지면(예: "17" → 1, 7, 17, 71), 만들 수 있는 모든 수 중 소수의 개수를 반환.

💡 접근

전체 흐름: ① 문자 분리 → ② DFS로 모든 순열 생성 → ③ Set에 저장(중복 제거) → ④ 소수 판별 → ⑤ 개수 반환.

1. 소수 판별 — 2 ~ √N까지만 N = a × b이면 a ≤ √N ≤ b이므로 √N까지만 나눠보면 충분하다. O(√N).

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

2. 순열 생성 — DFS + 백트래킹 문자를 하나씩 붙여 가며(append → 재귀 → delete) 모든 자리 조합을 만든다. visited[]도 재귀 후 반드시 복구한다.

3. 중복 제거 — Set<Integer> "011"처럼 중복 숫자가 있으면 같은 값이 여러 번 생기므로 Set으로 걸러낸다.

⌨️ 풀이

import java.util.HashSet;
import java.util.Set;
 
class Solution {
 
    private Set<Integer> numbers = new HashSet<>();
 
    public int solution(String input) {
        boolean[] visited = new boolean[input.length()];
        dfs("", input, visited);
 
        int count = 0;
        for (int num : numbers) {
            if (isPrime(num)) {
                count++;
            }
        }
        return count;
    }
 
    private void dfs(String current, String input, boolean[] visited) {
        if (!current.isEmpty()) {
            numbers.add(Integer.parseInt(current));
        }
 
        for (int i = 0; i < input.length(); i++) {
            if (visited[i]) continue;
 
            visited[i] = true;
            dfs(current + input.charAt(i), input, visited);
            visited[i] = false;
        }
    }
 
    private boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

⏱️ 복잡도

• 시간: 순열 생성이 O(N!)(N = 문자 길이) 수준 + 각 수의 소수 판별 O(√M). 문자열 길이 제한이 작아 통과.
• 공간: O(N) — 재귀 깊이와 방문 배열, 생성된 수를 담는 Set.

📎 DFS 작성 팁 (암기 템플릿)

for (모든 선택지) {
    if (이미 사용됨) continue;
    사용 처리 + 상태 변경;
    dfs();
    상태 복구 + 사용 복구;  // ★ 백트래킹
}

체크리스트: ① 종료(결과 저장) 위치 → ② 상태 변경 → ③ 재귀 → ④ 상태 복구.

---

🔗 관련

• (Algorithm) 타겟넘버 - 핵심 개념 및 특징 정리
• (Algorithm) 완전탐색-조합패턴 - 완전탐색조합패턴
• (Algorithm) N과 M(1) - 핵심 개념 및 특징 정리 — DFS/백트래킹 계열
• 소수 찾기 — 소수 판별 방식 비교(에라토스테네스의 체 vs DFS 순열+시행 나눗셈)
• (DFS) 백준 2023번 — DFS로 후보를 생성하며 소수를 판별하는 동일 패턴
• (DFS) 깊이우선탐색 — DFS/백트래킹 개념 원류
• (Algorithm) 60일 계획 - 핵심 개념 및 특징 정리 — 1~20일차 학습 커리큘럼에서 참조하는 문제